home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / TEMP / GNU / bison / MysteryCon < prev    next >
Text File  |  1995-06-28  |  3KB  |  106 lines
  1. Mystery Conflicts
  2. Previous: <Reduce\/Reduce=>ReduceRedv> * Next: <Stack Overflow=>StackOverf> * Up: <Algorithm=>Algorithm>
  3.  
  4. #Wrap on
  5. {fH3}Mysterious Reduce\/Reduce Conflicts{f}
  6.  
  7. Sometimes reduce\/reduce conflicts can occur that don't look warranted.
  8. Here is an example:
  9.  
  10. #Wrap off
  11. #fCode
  12. %token ID
  13.  
  14. %%
  15. def:    param\_spec return\_spec ','
  16.         ;
  17. param\_spec:
  18.              type
  19.         |    name\_list ':' type
  20.         ;
  21. return\_spec:
  22.              type
  23.         |    name ':' type
  24.         ;
  25. type:        ID
  26.         ;
  27. name:        ID
  28.         ;
  29. name\_list:
  30.              name
  31.         |    name ',' name\_list
  32.         ;
  33. #f
  34. #Wrap on
  35.  
  36. It would seem that this grammar can be parsed with only a single token
  37. of look-ahead: when a {fCode}param\_spec{f} is being read, an {fCode}ID{f} is 
  38. a {fCode}name{f} if a comma or colon follows, or a {fCode}type{f} if another
  39. {fCode}ID{f} follows.  In other words, this grammar is LR(1).
  40.  
  41. However, Bison, like most parser generators, cannot actually handle all
  42. LR(1) grammars.  In this grammar, two contexts, that after an {fCode}ID{f}
  43. at the beginning of a {fCode}param\_spec{f} and likewise at the beginning of
  44. a {fCode}return\_spec{f}, are similar enough that Bison assumes they are the
  45. same.  They appear similar because the same set of rules would be
  46. active---the rule for reducing to a {fCode}name{f} and that for reducing to
  47. a {fCode}type{f}.  Bison is unable to determine at that stage of processing
  48. that the rules would require different look-ahead tokens in the two
  49. contexts, so it makes a single parser state for them both.  Combining
  50. the two contexts causes a conflict later.  In parser terminology, this
  51. occurrence means that the grammar is not LALR(1).
  52.  
  53. In general, it is better to fix deficiencies than to document them.  But
  54. this particular deficiency is intrinsically hard to fix; parser
  55. generators that can handle LR(1) grammars are hard to write and tend to
  56. produce parsers that are very large.  In practice, Bison is more useful
  57. as it is now.
  58.  
  59. When the problem arises, you can often fix it by identifying the two
  60. parser states that are being confused, and adding something to make them
  61. look distinct.  In the above example, adding one rule to
  62. {fCode}return\_spec{f} as follows makes the problem go away:
  63.  
  64. #Wrap off
  65. #fCode
  66. %token BOGUS
  67. …
  68. %%
  69. …
  70. return\_spec:
  71.              type
  72.         |    name ':' type
  73.         \/\* This rule is never used.  \*\/
  74.         |    ID BOGUS
  75.         ;
  76. #f
  77. #Wrap on
  78.  
  79. This corrects the problem because it introduces the possibility of an
  80. additional active rule in the context after the {fCode}ID{f} at the beginning of
  81. {fCode}return\_spec{f}.  This rule is not active in the corresponding context
  82. in a {fCode}param\_spec{f}, so the two contexts receive distinct parser states.
  83. As long as the token {fCode}BOGUS{f} is never generated by {fCode}yylex{f},
  84. the added rule cannot alter the way actual input is parsed.
  85.  
  86. In this particular example, there is another way to solve the problem:
  87. rewrite the rule for {fCode}return\_spec{f} to use {fCode}ID{f} directly
  88. instead of via {fCode}name{f}.  This also causes the two confusing
  89. contexts to have different sets of active rules, because the one for
  90. {fCode}return\_spec{f} activates the altered rule for {fCode}return\_spec{f}
  91. rather than the one for {fCode}name{f}.
  92.  
  93. #Wrap off
  94. #fCode
  95. param\_spec:
  96.              type
  97.         |    name\_list ':' type
  98.         ;
  99. return\_spec:
  100.              type
  101.         |    ID ':' type
  102.         ;
  103. #f
  104. #Wrap on
  105.  
  106.